#include <vector>
#include <algorithm>
#include <iostream>
#include <windows.h>

using namespace std;

class Solution 
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        vector<vector<int>> results;
        sort(nums.begin(), nums.end());
        int length = nums.size();
        if(length < 4)
        {
            return results;
        }
        for(int i = 0; i < length - 3; i++)
        {
            if(i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }
            for(int j = i + 1; j < length - 2; j++)
            {
                if(j > i + 1 && nums[j] == nums[j - 1])
                {
                    continue;
                }
                int left = j + 1;
                int right = length - 1;
                while (left < right)
                {
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum < target)
                    {
                        left++;
                    }
                    else if(sum > target)
                    {
                        right--;
                    }
                    else
                    {
                        vector<int> result = {nums[i], nums[j], nums[left], nums[right]};
                        results.push_back(result);
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1])
                        {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1])
                        {
                            right--;
                        }
                    }
                }
            }
        }
        return results;
    }
};

int main()
{
    SetConsoleOutputCP(CP_UTF8);
    Solution solution;

    // 测试案例1: 基本四数之和案例
    vector<int> nums1 = {1, 0, -1, 0, -2, 2};
    int target1 = 0;
    vector<vector<int>> result1 = solution.fourSum(nums1, target1);
    cout << "测试案例1: nums = [1, 0, -1, 0, -2, 2], target = 0" << endl;
    cout << "结果:" << endl;
    for(const auto& quadruplet : result1) {
        cout << "[" << quadruplet[0] << ", " << quadruplet[1] << ", " << quadruplet[2] << ", " << quadruplet[3] << "]" << endl;
    }
    cout << endl;

    // 测试案例2: 有重复数字的案例
    vector<int> nums2 = {2, 2, 2, 2, 2};
    int target2 = 8;
    vector<vector<int>> result2 = solution.fourSum(nums2, target2);
    cout << "测试案例2: nums = [2, 2, 2, 2, 2], target = 8" << endl;
    cout << "结果:" << endl;
    for(const auto& quadruplet : result2) {
        cout << "[" << quadruplet[0] << ", " << quadruplet[1] << ", " << quadruplet[2] << ", " << quadruplet[3] << "]" << endl;
    }
    cout << endl;

    // 测试案例3: 无解案例（所有数都太大）
    vector<int> nums3 = {5, 5, 5, 5, 5};
    int target3 = 8;
    vector<vector<int>> result3 = solution.fourSum(nums3, target3);
    cout << "测试案例3: nums = [5, 5, 5, 5, 5], target = 8" << endl;
    cout << "结果:" << endl;
    for(const auto& quadruplet : result3) {
        cout << "[" << quadruplet[0] << ", " << quadruplet[1] << ", " << quadruplet[2] << ", " << quadruplet[3] << "]" << endl;
    }
    cout << endl;

    // 测试案例4: 边界案例（正好四个数）
    vector<int> nums4 = {-2, -1, 0, 1};
    int target4 = -1;
    vector<vector<int>> result4 = solution.fourSum(nums4, target4);
    cout << "测试案例4: nums = [-2, -1, 0, 1], target = -1" << endl;
    cout << "结果:" << endl;
    for(const auto& quadruplet : result4) {
        cout << "[" << quadruplet[0] << ", " << quadruplet[1] << ", " << quadruplet[2] << ", " << quadruplet[3] << "]" << endl;
    }
    cout << endl;

    // 测试案例5: LeetCode示例
    vector<int> nums5 = {1, -2, -5, -4, -3, 3, 3, 5};
    int target5 = -11;
    vector<vector<int>> result5 = solution.fourSum(nums5, target5);
    cout << "测试案例5: nums = [1, -2, -5, -4, -3, 3, 3, 5], target = -11" << endl;
    cout << "结果:" << endl;
    for(const auto& quadruplet : result5) {
        cout << "[" << quadruplet[0] << ", " << quadruplet[1] << ", " << quadruplet[2] << ", " << quadruplet[3] << "]" << endl;
    }
    cout << endl;

    // 测试案例6: 避免大数字溢出
    vector<int> nums6 = {-10000000, -10000000, -10000000, -10000000};
    int target6 = -40000000;
    vector<vector<int>> result6 = solution.fourSum(nums6, target6);
    cout << "测试案例6: nums = [-10000000, -10000000, -10000000, -10000000], target = -40000000" << endl;
    cout << "结果:" << endl;
    for(const auto& quadruplet : result6) {
        cout << "[" << quadruplet[0] << ", " << quadruplet[1] << ", " << quadruplet[2] << ", " << quadruplet[3] << "]" << endl;
    }
    cout << endl;

    return 0;
}